import java.util.ArrayDeque;
import java.util.Deque;

/*
 * @lc app=leetcode.cn id=1047 lang=java
 *
 * [1047] 删除字符串中的所有相邻重复项
 */

// @lc code=start
class Solution {
    public String removeDuplicates(String s) {
        Deque<Character> stack=new ArrayDeque<>();
        for(char ch:s.toCharArray()){
            if(stack.isEmpty()||stack.peek()!=ch){
                stack.push(ch);
            }else{
                stack.pop();
            }
        }
        String res="";
        while(!stack.isEmpty()){
            res=stack.pop()+res;
        }
        return res;
         
    }
}
//二刷
// class Solution {
//     public String removeDuplicates(String s) {
//         Deque<Character> stack=new LinkedList<>();
//         for(char c:s.toCharArray()){
//             if(!stack.isEmpty()&&stack.peek()==c){
//                 stack.pop();
//             }else{
//                 stack.push(c);
//             }
//         }
//         StringBuilder b=new StringBuilder();
//         while(!stack.isEmpty()){
//             b.append(stack.pop());
//         }
//         return b.reverse().toString();
//     }
// }
// @lc code=end

